/*************************************************************************************
* qTESLA: an efficient post-quantum signature scheme based on the R-LWE problem
*
* Merged together in one file for OQS inclusion, made all functions static except
* the api.h ones, and renamed them.
**************************************************************************************/
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <oqs/rand.h>
#include <oqs/sha3.h>
#include "qTESLA_III_speed.h"

/* params.h */

#define PARAM_N 1024
#define PARAM_N_LOG 10
#define PARAM_SIGMA 10.2
#define PARAM_Xi 12
#define PARAM_Q 8404993
#define PARAM_Q_LOG 24
#define PARAM_QINV 4034936831
#define PARAM_BARR_MULT 511
#define PARAM_BARR_DIV 32
#define PARAM_B 2097151
#define PARAM_B_BITS 21

#define PARAM_K 1
#define PARAM_SIGMA_E PARAM_SIGMA

#define PARAM_W 48
#define PARAM_D 22

#define PARAM_GEN_A 38

#define PARAM_KEYGEN_BOUND_E 1147
#define PARAM_REJECTION PARAM_KEYGEN_BOUND_E
#define PARAM_KEYGEN_BOUND_S 1233
#define PARAM_U PARAM_KEYGEN_BOUND_S

#define PARAM_R2_INVN 237839

/* poly.h */

typedef int64_t __attribute__((aligned(32))) poly[PARAM_N];

static int64_t reduce(int64_t a);
static int32_t barr_reduce(int64_t a);
static void ntt(poly a, const poly w);
static void nttinv(poly a, const poly w);
static void poly_mul(poly result, const poly x, const poly y);
static void poly_add(poly result, const poly x, const poly y);
static void poly_sub(poly result, const poly x, const poly y);
static void poly_uniform(poly a, const unsigned char *seed);

/* api.h */

#define CRYPTO_RANDOMBYTES 32
#define CRYPTO_SEEDBYTES 32
#define CRYPTO_C_BYTES 32

// Contains signature (z,c). z is a polynomial bounded by B, c is the output of a hashed string
#define CRYPTO_BYTES ((PARAM_N * PARAM_D + 7) / 8 + CRYPTO_C_BYTES)
// Contains polynomial s and e, and seeds seed_a and seed_y
#define CRYPTO_SECRETKEYBYTES (2 * sizeof(int16_t) * PARAM_N + 2 * CRYPTO_SEEDBYTES)
// Contains seed_a and polynomial t
#define CRYPTO_PUBLICKEYBYTES ((PARAM_N * PARAM_Q_LOG + 7) / 8 + CRYPTO_SEEDBYTES)

#define CRYPTO_ALGNAME "qTesla-III-speed"

/* sample.h */

static void sample_y(int64_t *y, const unsigned char *seed, int nonce);
static void sample_gauss_poly(int64_t *x, const unsigned char *seed, int nonce);
static void encode_c(uint32_t *pos_list, int16_t *sign_list, unsigned char *c_bin);

/* const.c */

static poly zeta = {

    4751355, 3795849, 4203855, 2135008, 6005859, 8231721, 5028848, 2129664, 7697675, 4755217, 4725508, 3239612, 6448681, 1076080, 3836135, 157994,
    5620931, 7886062, 2890907, 5218426, 5961785, 6266756, 6428554, 5190121, 4542230, 1731429, 2223635, 4784194, 3466184, 2050685, 6391390, 2917454,
    2117568, 5724978, 3127077, 96284, 5251989, 3298678, 7201703, 432021, 540694, 6011377, 6511091, 6136825, 215125, 6152822, 4121955, 6320948,
    4723419, 3116754, 3645529, 4643271, 3249093, 3697259, 965302, 3790255, 413429, 835404, 7555714, 4708344, 980578, 8245349, 3583234, 5891188,
    510086, 5483952, 4214513, 7522675, 1382737, 8097349, 2423268, 1978286, 5820434, 2985005, 1002240, 3252040, 5584283, 4027445, 3761478, 571563,
    7926529, 5265675, 4705738, 1136608, 2087977, 4856723, 7896505, 2504130, 4175968, 5245926, 3848909, 3723902, 2181242, 6476735, 5922041, 2555482,
    6087709, 1106974, 975919, 978505, 666303, 510879, 5043449, 4402981, 4204183, 6947226, 3519239, 7237093, 2533941, 1259684, 4897608, 2422013,
    5398162, 3551190, 6378523, 1066751, 5216741, 6557683, 7171180, 7736022, 7762004, 7816398, 434930, 5685531, 7776512, 2136107, 4689096, 2604202,
    981324, 6730872, 7113462, 4313227, 5315069, 2687514, 6464663, 6622027, 4919554, 3137828, 6662263, 180027, 1225049, 993103, 6035200, 4768729,
    7594608, 7982166, 1506084, 1412996, 7294988, 6493396, 3679803, 707143, 5016089, 5893370, 7746168, 8284307, 2196442, 4506697, 5744441, 8155374,
    2335696, 3358969, 4559736, 8378847, 7396599, 5613912, 5146767, 5609330, 7478110, 7007768, 1540167, 2082109, 4395136, 2443, 1730472, 6785605,
    3689430, 7862069, 5994777, 2079150, 1569788, 3575961, 2449565, 7637802, 3223577, 7636917, 7014221, 3206599, 1033702, 2788915, 2962522, 5785994,
    2935623, 8040165, 646639, 6994735, 1576929, 4976182, 1923760, 7349612, 7767222, 5695773, 2143434, 1957445, 6164911, 6325092, 3612819, 5415356,
    6956649, 426840, 6748291, 3530533, 2487417, 7851363, 3671732, 7201581, 4717139, 4328822, 5046010, 6056773, 997476, 3549222, 1616322, 3335537,
    2012692, 7475529, 2140630, 167787, 3791455, 3347958, 1263751, 2818658, 8280316, 4667491, 7207537, 6918648, 6602507, 1441518, 5135376, 1610367,
    1016061, 6841480, 1841539, 2809077, 5412381, 1240493, 4442913, 2092171, 530239, 4308557, 3094305, 18124, 7247221, 5096652, 6892131, 3384856,
    1435046, 3360331, 4908655, 1534384, 724138, 4632705, 7021901, 776577, 6462800, 658408, 6767742, 6323190, 163450, 3090558, 8264681, 6113406,
    2256514, 2002774, 4157811, 1055743, 4272701, 50782, 506820, 2425609, 6121916, 7048118, 7211758, 7436523, 7921267, 8219231, 2113012, 5561555,
    5402793, 6238877, 2785469, 6601179, 5379488, 8247469, 7039082, 8122949, 4032315, 7719142, 6412117, 1765474, 1423373, 3702073, 6814517, 4539579,
    3714409, 3581714, 4818181, 4950204, 6549391, 6746510, 1332314, 6200219, 4026957, 4085009, 6474721, 6328096, 8097370, 821395, 4479068, 6408341,
    1730278, 3865108, 131998, 3351400, 4527559, 4193606, 1952686, 3339484, 549242, 3890467, 3314638, 2970830, 7867854, 235273, 4948941, 3082658,
    6487691, 6448908, 3822702, 5156099, 3762420, 359477, 1160634, 2545064, 2616573, 343964, 1277910, 8113538, 5564704, 6944366, 2663139, 2516714,
    7942808, 5983628, 6727371, 7839582, 4671024, 5279277, 2488251, 5096610, 7584873, 1054559, 3389302, 5410955, 2700464, 7113783, 1182446, 681631,
    7959149, 1325409, 3882231, 4559, 7653722, 2600940, 4354328, 6155200, 8125241, 629708, 1056841, 5566349, 6779032, 7067599, 5284661, 693330,
    7111640, 6054764, 513663, 3702555, 3667331, 8053262, 3156410, 3207020, 6096921, 3226364, 425916, 1538990, 398369, 155207, 5962206, 3895624,
    3506460, 4470299, 8132637, 7313282, 1829556, 3023684, 7819374, 258083, 4547318, 6274233, 4376026, 630321, 5354666, 3252030, 3347795, 5465400,
    424523, 5150532, 4329513, 5096843, 2541091, 4590781, 5698802, 5642789, 6737542, 6616826, 6654175, 1804189, 2843875, 5019191, 2161010, 1581450,
    7289320, 4525144, 2861293, 1184843, 6181826, 3408399, 6954125, 5897789, 899044, 983144, 996950, 2489509, 387143, 6743865, 6535741, 5316114,
    2464958, 6452453, 6588356, 7749117, 3100483, 5451553, 6683005, 6153131, 2627493, 3750459, 6016367, 1854681, 5732487, 5756336, 8222984, 6286073,
    4805023, 4851345, 5346259, 2571898, 7886466, 915166, 750162, 7786158, 3314583, 3691654, 8162728, 2964553, 934173, 2078087, 5894912, 103974,
    2087696, 8074875, 5687948, 6220280, 5741269, 3408244, 5908533, 5524440, 405672, 2691224, 4107404, 1478212, 5069278, 1307718, 2701016, 5020579,
    3281802, 173449, 7661012, 6737317, 2871182, 7099172, 8035102, 4259638, 676548, 1986555, 2711904, 72486, 1537417, 4903843, 6366739, 2767425,
    4405806, 3939004, 6029482, 7042007, 7145803, 4423846, 5865280, 6985580, 4890457, 5525519, 3020926, 5286410, 2507470, 164000, 7418741, 3860720,
    464246, 7532333, 2980645, 2208123, 1971493, 7819798, 4391480, 3562255, 1579560, 3499404, 3220123, 5084410, 2287245, 6505523, 7780056, 63470,
    7361152, 6336292, 3791465, 1891129, 6121738, 6215206, 578317, 2487175, 2862407, 7213504, 175006, 850302, 4374314, 3335934, 5070337, 6404001,
    6073674, 8339498, 2024643, 590809, 3871922, 7695009, 3420134, 2417242, 2441851, 510359, 6415975, 5966400, 1511640, 3278055, 7552659, 7251424,
    299565, 4631182, 923500, 4565103, 1774136, 1514014, 504288, 7611114, 348434, 6179273, 6103289, 5512004, 6204874, 4163633, 4030619, 5442160,
    5517078, 4979705, 1450139, 4955279, 6892996, 1378796, 7049658, 7482552, 2773460, 3700106, 5637962, 1306126, 1342831, 2876039, 2004802, 7911534,
    7811881, 7092783, 2948733, 3985770, 4334975, 2089910, 4202878, 5889243, 2572806, 7276150, 3116397, 4610309, 4197207, 4524762, 3158380, 712800,
    7767402, 2288328, 3468435, 4486610, 3258256, 4642983, 4397184, 3897150, 3551813, 5337205, 7602723, 882125, 4202004, 8272524, 4429435, 2663261,
    1849803, 4271342, 947283, 5290695, 2673376, 7191822, 2383684, 5913757, 1682056, 4777883, 695434, 2390033, 5758581, 3482483, 6148624, 4372212,
    1400527, 3325425, 3100142, 7502466, 6912369, 6564003, 187779, 6691298, 1850484, 1886083, 496958, 4353128, 6385269, 7972087, 3249950, 1216051,
    2945392, 1716654, 974864, 2073675, 4221586, 3197564, 5970107, 2900682, 1387771, 1054897, 5018658, 4773826, 2772495, 3056563, 3437397, 1151634,
    3999643, 4238788, 2370183, 7770204, 2300657, 4762800, 4526771, 4778855, 6276244, 2113067, 4081453, 4596532, 896126, 1589159, 5012357, 1884715,
    3849142, 1866468, 1032092, 4847686, 5661618, 424095, 6396824, 6683872, 1861112, 2415218, 7008299, 7999725, 61635, 7831813, 1934052, 1635771,
    5857904, 3890446, 3661009, 4427825, 1472600, 2675631, 3142762, 2889031, 6246428, 3402870, 890885, 300722, 6084442, 6218398, 6764876, 198422,
    5203148, 1220540, 3348691, 7973167, 1045857, 5930282, 7686549, 4965437, 2645402, 3029580, 1825802, 4844838, 5808305, 3553948, 2913430, 4640069,
    3231039, 5061776, 3388089, 5793791, 5210767, 6179591, 3259669, 208882, 7981542, 8176212, 8044267, 4362411, 8164807, 3882310, 4575856, 1654989,
    2265125, 4993003, 1845358, 876204, 4604356, 6572234, 3709582, 2495322, 7769694, 925160, 5211127, 3071339, 8271814, 1715113, 5979772, 8317560,
    2452182, 4560530, 2756321, 7541123, 2085235, 2131014, 7043807, 945796, 1043611, 2220162, 1519639, 1881321, 4596482, 136652, 8225264, 4442429,
    3140394, 4274467, 2235364, 3403641, 181254, 2256107, 5402447, 274444, 2450384, 774651, 1007857, 488393, 7305342, 8006923, 6213033, 6045031,
    7357074, 3686418, 2069641, 4827274, 6134510, 8182850, 6622239, 4957796, 5001496, 2676491, 2165891, 4258696, 1805202, 5978874, 5892091, 3081817,
    8351892, 2919790, 6813596, 1226235, 7874664, 1597662, 445691, 7699844, 517985, 5142533, 583275, 2942212, 2005170, 2781492, 5325095, 5840485,
    5904531, 1652696, 462001, 488382, 1483208, 3583371, 3903552, 4338246, 8102054, 4607027, 3097235, 5461223, 878707, 5641705, 3004044, 6269117,
    8310809, 1068150, 3754674, 7419023, 2389012, 2672920, 7033357, 3299934, 5696831, 8333890, 6870124, 4248890, 7451238, 2996873, 969409, 4748469,
    6761147, 7334152, 4608897, 6381766, 593469, 5060352, 7663929, 3490012, 5639842, 804562, 3554683, 1275119, 2464713, 584123, 1282802, 869246,
    1698712, 460380, 2270294, 1082297, 5755881, 4164200, 3083595, 7232256, 6669791, 5297513, 7888160, 305159, 4943995, 4839451, 4607217, 4607189,
    4027370, 6773057, 2930951, 7228212, 4930292, 5787132, 6979166, 3679768, 2488882, 7434774, 6751191, 4901863, 601751, 3772392, 4470584, 3139313,
    2581011, 5344571, 2578160, 126930, 4080823, 5594812, 3191131, 2170321, 4703512, 3837804, 7417071, 2996858, 6019670, 5239573, 1770901, 7113857,
    5965467, 8008016, 192380, 7790747, 867783, 2310931, 477474, 723267, 2025346, 7474446, 1992778, 5665730, 5375937, 1925098, 1772156, 7957977,
    7842750, 4780661, 1703317, 4165961, 5256458, 4850569, 4937646, 1616991, 8229940, 128563, 1160620, 5109082, 4794032, 4890146, 4147576, 7912097,
    927266, 450684, 7302719, 2598976, 5529718, 1041149, 4841395, 6276135, 7825395, 7621671, 6329777, 1955851, 6040427, 1035300, 2855476, 3258870,
    3396861, 5274746, 2777694, 3359337, 4493563, 561924, 7215951, 2907115, 4547697, 5403413, 7025806, 2453538, 4137455, 971005, 4298903, 1271923,
    7150549, 2833306, 8021667, 7587207, 833119, 2919663, 5306176, 659188, 4708953, 3799478, 5584025, 7305039, 5709959, 3562365, 965949, 15873,
};
static poly zetainv = {

    7439044, 4842628, 2695034, 1099954, 2820968, 4605515, 3696040, 7745805, 3098817, 5485330, 7571874, 817786, 383326, 5571687, 1254444, 7133070,
    4106090, 7433988, 4267538, 5951455, 1379187, 3001580, 3857296, 5497878, 1189042, 7843069, 3911430, 5045656, 5627299, 3130247, 5008132, 5146123,
    5549517, 7369693, 2364566, 6449142, 2075216, 783322, 579598, 2128858, 3563598, 7363844, 2875275, 5806017, 1102274, 7954309, 7477727, 492896,
    4257417, 3514847, 3610961, 3295911, 7244373, 8276430, 175053, 6788002, 3467347, 3554424, 3148535, 4239032, 6701676, 3624332, 562243, 447016,
    6632837, 6479895, 3029056, 2739263, 6412215, 930547, 6379647, 7681726, 7927519, 6094062, 7537210, 614246, 8212613, 396977, 2439526, 1291136,
    6634092, 3165420, 2385323, 5408135, 987922, 4567189, 3701481, 6234672, 5213862, 2810181, 4324170, 8278063, 5826833, 3060422, 5823982, 5265680,
    3934409, 4632601, 7803242, 3503130, 1653802, 970219, 5916111, 4725225, 1425827, 2617861, 3474701, 1176781, 5474042, 1631936, 4377623, 3797804,
    3797776, 3565542, 3460998, 8099834, 516833, 3107480, 1735202, 1172737, 5321398, 4240793, 2649112, 7322696, 6134699, 7944613, 6706281, 7535747,
    7122191, 7820870, 5940280, 7129874, 4850310, 7600431, 2765151, 4914981, 741064, 3344641, 7811524, 2023227, 3796096, 1070841, 1643846, 3656524,
    7435584, 5408120, 953755, 4156103, 1534869, 71103, 2708162, 5105059, 1371636, 5732073, 6015981, 985970, 4650319, 7336843, 94184, 2135876,
    5400949, 2763288, 7526286, 2943770, 5307758, 3797966, 302939, 4066747, 4501441, 4821622, 6921785, 7916611, 7942992, 6752297, 2500462, 2564508,
    3079898, 5623501, 6399823, 5462781, 7821718, 3262460, 7887008, 705149, 7959302, 6807331, 530329, 7178758, 1591397, 5485203, 53101, 5323176,
    2512902, 2426119, 6599791, 4146297, 6239102, 5728502, 3403497, 3447197, 1782754, 222143, 2270483, 3577719, 6335352, 4718575, 1047919, 2359962,
    2191960, 398070, 1099651, 7916600, 7397136, 7630342, 5954609, 8130549, 3002546, 6148886, 8223739, 5001352, 6169629, 4130526, 5264599, 3962564,
    179729, 8268341, 3808511, 6523672, 6885354, 6184831, 7361382, 7459197, 1361186, 6273979, 6319758, 863870, 5648672, 3844463, 5952811, 87433,
    2425221, 6689880, 133179, 5333654, 3193866, 7479833, 635299, 5909671, 4695411, 1832759, 3800637, 7528789, 6559635, 3411990, 6139868, 6750004,
    3829137, 4522683, 240186, 4042582, 360726, 228781, 423451, 8196111, 5145324, 2225402, 3194226, 2611202, 5016904, 3343217, 5173954, 3764924,
    5491563, 4851045, 2596688, 3560155, 6579191, 5375413, 5759591, 3439556, 718444, 2474711, 7359136, 431826, 5056302, 7184453, 3201845, 8206571,
    1640117, 2186595, 2320551, 8104271, 7514108, 5002123, 2158565, 5515962, 5262231, 5729362, 6932393, 3977168, 4743984, 4514547, 2547089, 6769222,
    6470941, 573180, 8343358, 405268, 1396694, 5989775, 6543881, 1721121, 2008169, 7980898, 2743375, 3557307, 7372901, 6538525, 4555851, 6520278,
    3392636, 6815834, 7508867, 3808461, 4323540, 6291926, 2128749, 3626138, 3878222, 3642193, 6104336, 634789, 6034810, 4166205, 4405350, 7253359,
    4967596, 5348430, 5632498, 3631167, 3386335, 7350096, 7017222, 5504311, 2434886, 5207429, 4183407, 6331318, 7430129, 6688339, 5459601, 7188942,
    5155043, 432906, 2019724, 4051865, 7908035, 6518910, 6554509, 1713695, 8217214, 1840990, 1492624, 902527, 5304851, 5079568, 7004466, 4032781,
    2256369, 4922510, 2646412, 6014960, 7709559, 3627110, 6722937, 2491236, 6021309, 1213171, 5731617, 3114298, 7457710, 4133651, 6555190, 5741732,
    3975558, 132469, 4202989, 7522868, 802270, 3067788, 4853180, 4507843, 4007809, 3762010, 5146737, 3918383, 4936558, 6116665, 637591, 7692193,
    5246613, 3880231, 4207786, 3794684, 5288596, 1128843, 5832187, 2515750, 4202115, 6315083, 4070018, 4419223, 5456260, 1312210, 593112, 493459,
    6400191, 5528954, 7062162, 7098867, 2767031, 4704887, 5631533, 922441, 1355335, 7026197, 1511997, 3449714, 6954854, 3425288, 2887915, 2962833,
    4374374, 4241360, 2200119, 2892989, 2301704, 2225720, 8056559, 793879, 7900705, 6890979, 6630857, 3839890, 7481493, 3773811, 8105428, 1153569,
    852334, 5126938, 6893353, 2438593, 1989018, 7894634, 5963142, 5987751, 4984859, 709984, 4533071, 7814184, 6380350, 65495, 2331319, 2000992,
    3334656, 5069059, 4030679, 7554691, 8229987, 1191489, 5542586, 5917818, 7826676, 2189787, 2283255, 6513864, 4613528, 2068701, 1043841, 8341523,
    624937, 1899470, 6117748, 3320583, 5184870, 4905589, 6825433, 4842738, 4013513, 585195, 6433500, 6196870, 5424348, 872660, 7940747, 4544273,
    986252, 8240993, 5897523, 3118583, 5384067, 2879474, 3514536, 1419413, 2539713, 3981147, 1259190, 1362986, 2375511, 4465989, 3999187, 5637568,
    2038254, 3501150, 6867576, 8332507, 5693089, 6418438, 7728445, 4145355, 369891, 1305821, 5533811, 1667676, 743981, 8231544, 5123191, 3384414,
    5703977, 7097275, 3335715, 6926781, 4297589, 5713769, 7999321, 2880553, 2496460, 4996749, 2663724, 2184713, 2717045, 330118, 6317297, 8301019,
    2510081, 6326906, 7470820, 5440440, 242265, 4713339, 5090410, 618835, 7654831, 7489827, 518527, 5833095, 3058734, 3553648, 3599970, 2118920,
    182009, 2648657, 2672506, 6550312, 2388626, 4654534, 5777500, 2251862, 1721988, 2953440, 5304510, 655876, 1816637, 1952540, 5940035, 3088879,
    1869252, 1661128, 8017850, 5915484, 7408043, 7421849, 7505949, 2507204, 1450868, 4996594, 2223167, 7220150, 5543700, 3879849, 1115673, 6823543,
    6243983, 3385802, 5561118, 6600804, 1750818, 1788167, 1667451, 2762204, 2706191, 3814212, 5863902, 3308150, 4075480, 3254461, 7980470, 2939593,
    5057198, 5152963, 3050327, 7774672, 4028967, 2130760, 3857675, 8146910, 585619, 5381309, 6575437, 1091711, 272356, 3934694, 4898533, 4509369,
    2442787, 8249786, 8006624, 6866003, 7979077, 5178629, 2308072, 5197973, 5248583, 351731, 4737662, 4702438, 7891330, 2350229, 1293353, 7711663,
    3120332, 1337394, 1625961, 2838644, 7348152, 7775285, 279752, 2249793, 4050665, 5804053, 751271, 8400434, 4522762, 7079584, 445844, 7723362,
    7222547, 1291210, 5704529, 2994038, 5015691, 7350434, 820120, 3308383, 5916742, 3125716, 3733969, 565411, 1677622, 2421365, 462185, 5888279,
    5741854, 1460627, 2840289, 291455, 7127083, 8061029, 5788420, 5859929, 7244359, 8045516, 4642573, 3248894, 4582291, 1956085, 1917302, 5322335,
    3456052, 8169720, 537139, 5434163, 5090355, 4514526, 7855751, 5065509, 6452307, 4211387, 3877434, 5053593, 8272995, 4539885, 6674715, 1996652,
    3925925, 7583598, 307623, 2076897, 1930272, 4319984, 4378036, 2204774, 7072679, 1658483, 1855602, 3454789, 3586812, 4823279, 4690584, 3865414,
    1590476, 4702920, 6981620, 6639519, 1992876, 685851, 4372678, 282044, 1365911, 157524, 3025505, 1803814, 5619524, 2166116, 3002200, 2843438,
    6291981, 185762, 483726, 968470, 1193235, 1356875, 2283077, 5979384, 7898173, 8354211, 4132292, 7349250, 4247182, 6402219, 6148479, 2291587,
    140312, 5314435, 8241543, 2081803, 1637251, 7746585, 1942193, 7628416, 1383092, 3772288, 7680855, 6870609, 3496338, 5044662, 6969947, 5020137,
    1512862, 3308341, 1157772, 8386869, 5310688, 4096436, 7874754, 6312822, 3962080, 7164500, 2992612, 5595916, 6563454, 1563513, 7388932, 6794626,
    3269617, 6963475, 1802486, 1486345, 1197456, 3737502, 124677, 5586335, 7141242, 5057035, 4613538, 8237206, 6264363, 929464, 6392301, 5069456,
    6788671, 4855771, 7407517, 2348220, 3358983, 4076171, 3687854, 1203412, 4733261, 553630, 5917576, 4874460, 1656702, 7978153, 1448344, 2989637,
    4792174, 2079901, 2240082, 6447548, 6261559, 2709220, 637771, 1055381, 6481233, 3428811, 6828064, 1410258, 7758354, 364828, 5469370, 2618999,
    5442471, 5616078, 7371291, 5198394, 1390772, 768076, 5181416, 767191, 5955428, 4829032, 6835205, 6325843, 2410216, 542924, 4715563, 1619388,
    6674521, 8402550, 4009857, 6322884, 6864826, 1397225, 926883, 2795663, 3258226, 2791081, 1008394, 26146, 3845257, 5046024, 6069297, 249619,
    2660552, 3898296, 6208551, 120686, 658825, 2511623, 3388904, 7697850, 4725190, 1911597, 1110005, 6991997, 6898909, 422827, 810385, 3636264,
    2369793, 7411890, 7179944, 8224966, 1742730, 5267165, 3485439, 1782966, 1940330, 5717479, 3089924, 4091766, 1291531, 1674121, 7423669, 5800791,
    3715897, 6268886, 628481, 2719462, 7970063, 588595, 642989, 668971, 1233813, 1847310, 3188252, 7338242, 2026470, 4853803, 3006831, 5982980,
    3507385, 7145309, 5871052, 1167900, 4885754, 1457767, 4200810, 4002012, 3361544, 7894114, 7738690, 7426488, 7429074, 7298019, 2317284, 5849511,
    2482952, 1928258, 6223751, 4681091, 4556084, 3159067, 4229025, 5900863, 508488, 3548270, 6317016, 7268385, 3699255, 3139318, 478464, 7833430,
    4643515, 4377548, 2820710, 5152953, 7402753, 5419988, 2584559, 6426707, 5981725, 307644, 7022256, 882318, 4190480, 2921041, 7894907, 2513805,
    4821759, 159644, 7424415, 3696649, 849279, 7569589, 7991564, 4614738, 7439691, 4707734, 5155900, 3761722, 4759464, 5288239, 3681574, 2084045,
    4283038, 2252171, 8189868, 2268168, 1893902, 2393616, 7864299, 7972972, 1203290, 5106315, 3153004, 8308709, 5277916, 2680015, 6287425, 5487539,
    2013603, 6354308, 4938809, 3620799, 6181358, 6673564, 3862763, 3214872, 1976439, 2138237, 2443208, 3186567, 5514086, 518931, 2784062, 8246999,
    4568858, 7328913, 1956312, 5165381, 3679485, 3649776, 707318, 6275329, 3376145, 173272, 2399134, 6269985, 4201138, 4609144, 3653638, 8389120,
};

/* poly.c */

static int64_t reduce(int64_t a) { // Montgomery reduction
	int64_t u;

	u = (a * PARAM_QINV) & 0xFFFFFFFF;
	u *= PARAM_Q;
	a += u;
	return a >> 32;
}

static int32_t barr_reduce(int64_t a) { // Barrett reduction
	int64_t u = ((a * PARAM_BARR_MULT) >> PARAM_BARR_DIV) * PARAM_Q;
	return a - u;
}

static void ntt(poly a, const poly w) { // Forward NTT transform
	int NumoProblems = PARAM_N >> 1, jTwiddle = 0;

	for (; NumoProblems > 0; NumoProblems >>= 1) {
		int jFirst, j = 0;
		for (jFirst = 0; jFirst < PARAM_N; jFirst = j + NumoProblems) {
			int W = w[jTwiddle++];
			for (j = jFirst; j < jFirst + NumoProblems; j++) {
				int temp = reduce(W * a[j + NumoProblems]);
				a[j + NumoProblems] = a[j] + (PARAM_Q - temp);
				a[j] = temp + a[j];
			}
		}
	}
}

static void nttinv(poly a, const poly w) { // Inverse NTT transform
	int NumoProblems = 1, jTwiddle = 0;
	for (NumoProblems = 1; NumoProblems < PARAM_N; NumoProblems *= 2) {
		int jFirst, j = 0;
		for (jFirst = 0; jFirst < PARAM_N; jFirst = j + NumoProblems) {
			int W = w[jTwiddle++];
			for (j = jFirst; j < jFirst + NumoProblems; j++) {
				int temp = a[j];
				a[j] = (temp + a[j + NumoProblems]);
				a[j + NumoProblems] = reduce(W * (temp + (2 * PARAM_Q - a[j + NumoProblems])));
			}
		}
		NumoProblems *= 2;
		for (jFirst = 0; jFirst < PARAM_N; jFirst = j + NumoProblems) {
			int W = w[jTwiddle++];
			for (j = jFirst; j < jFirst + NumoProblems; j++) {
				int temp = a[j];
				a[j] = barr_reduce(temp + a[j + NumoProblems]);
				a[j + NumoProblems] = reduce(W * (temp + (2 * PARAM_Q - a[j + NumoProblems])));
			}
		}
	}
}

static void poly_pointwise(poly result, const poly x, const poly y) { // Pointwise polynomial multiplication result = x.y
	unsigned int i;

	for (i = 0; i < PARAM_N; i++)
		result[i] = reduce(x[i] * y[i]);
}

static void poly_mul(poly result, const poly x, const poly y) { // Polynomial multiplication result = x*y, with in place reduction for (X^N+1)
	// The input x is assumed to be in NTT form
	poly y_ntt;

	for (int i = 0; i < PARAM_N; i++)
		y_ntt[i] = y[i];

	ntt(y_ntt, zeta);
	poly_pointwise(result, x, y_ntt);
	nttinv(result, zetainv);
}

static void poly_add(poly result, const poly x, const poly y) { // Polynomial addition result = x+y
	unsigned int i;

	for (i = 0; i < PARAM_N; i++)
		result[i] = x[i] + y[i];
}

static void poly_sub(poly result, const poly x, const poly y) { // Polynomial subtraction result = x-y
	unsigned int i;

	for (i = 0; i < PARAM_N; i++)
		result[i] = barr_reduce(x[i] + (2 * PARAM_Q - y[i]));
}

static void poly_uniform(poly a, const unsigned char *seed) { // Generation of polynomial "a"
	unsigned int pos = 0, i = 0, nbytes = (PARAM_Q_LOG + 7) / 8;
	unsigned int nblocks = PARAM_GEN_A;
	uint32_t val1, val2, val3, val4, mask = (1 << PARAM_Q_LOG) - 1;
	unsigned char buf[OQS_SHA3_SHAKE128_RATE * nblocks];
	uint16_t dmsp = 0;

	OQS_SHA3_cshake128_simple(buf, OQS_SHA3_SHAKE128_RATE * nblocks, dmsp++, seed, CRYPTO_RANDOMBYTES);

	while (i < PARAM_N) {
		if (pos > OQS_SHA3_SHAKE128_RATE * nblocks - 4 * nbytes) {
			nblocks = 1;
			OQS_SHA3_cshake128_simple(buf, OQS_SHA3_SHAKE128_RATE * nblocks, dmsp++, seed, CRYPTO_RANDOMBYTES);
			pos = 0;
		}
		val1 = (*(uint32_t *) (buf + pos)) & mask;
		pos += nbytes;
		val2 = (*(uint32_t *) (buf + pos)) & mask;
		pos += nbytes;
		val3 = (*(uint32_t *) (buf + pos)) & mask;
		pos += nbytes;
		val4 = (*(uint32_t *) (buf + pos)) & mask;
		pos += nbytes;
		if (val1 < PARAM_Q && i < PARAM_N)
			a[i++] = reduce((int64_t) val1 * PARAM_R2_INVN);
		if (val2 < PARAM_Q && i < PARAM_N)
			a[i++] = reduce((int64_t) val2 * PARAM_R2_INVN);
		if (val3 < PARAM_Q && i < PARAM_N)
			a[i++] = reduce((int64_t) val3 * PARAM_R2_INVN);
		if (val4 < PARAM_Q && i < PARAM_N)
			a[i++] = reduce((int64_t) val4 * PARAM_R2_INVN);
	}
}

/* sample.c */

#define round_double(x) (uint64_t)(x + 0.5)
#define NBLOCKS_SHAKE256 OQS_SHA3_SHAKE256_RATE / (((PARAM_B_BITS + 1) + 7) / 8)

static void sample_y(int64_t *y, const unsigned char *seed, int nonce) { // Sample polynomial y, such that each coefficient is in the range [-B,B]
	unsigned int i = 0, pos = 0, nblocks = PARAM_N;
	unsigned int nbytes = ((PARAM_B_BITS + 1) + 7) / 8;
	unsigned char buf[PARAM_N * nbytes];
	int16_t dmsp = (int16_t)(nonce << 8);

	OQS_SHA3_cshake256_simple((uint8_t *) buf, PARAM_N * nbytes, dmsp++, seed, CRYPTO_RANDOMBYTES);

	while (i < PARAM_N) {
		if (pos >= nblocks * nbytes) {
			nblocks = NBLOCKS_SHAKE256;
			OQS_SHA3_cshake256_simple((uint8_t *) buf, OQS_SHA3_SHAKE256_RATE, dmsp++, seed, CRYPTO_RANDOMBYTES);
			pos = 0;
		}
		y[i] = (*(uint32_t *) (buf + pos)) & ((1 << (PARAM_B_BITS + 1)) - 1);
		y[i] -= PARAM_B;
		if (y[i] != (1 << PARAM_B_BITS))
			i++;
		pos += nbytes;
	}
}

static int64_t mod7(int64_t k) { // Compute k modulo 7
	int64_t i = k;

	for (int j = 0; j < 2; j++) {
		i = (i & 7) + (i >> 3);
	}
	// i <= 7 at this point. If (i == 7) return 0, else return i
	return ((i - 7) >> 3) & i;
}

static uint32_t Bernoulli(int64_t r, int64_t t) { // Sample a bit from Bernoulli
	                                              // Restriction: 20-bit exponent
	static const double exp[3][32] = {
	    {
	        1.000000000000000000000000000000000000000,
	        0.9951980443443537316500388424172839303752,
	        0.9904191474668262564830185894967173613892,
	        0.9856631986401875746675941557587114196642,
	        0.9809300876689149347041557365309129923940,
	        0.9762197048866395987965541168345276706016,
	        0.9715319411536058687432894158212596709598,
	        0.9668666878541423134736924881553750396380,
	        0.9622238368941451396373408016639000521875,
	        0.9576032806985736469363056351479270970296,
	        0.9530049122089577101698314104664824876542,
	        0.9484286248809172302397073765744987564880,
	        0.9438743126816934966419131566675496907225,
	        0.9393418700876924042461092785035073150884,
	        0.9348311920820394674392081270253399758265,
	        0.9303421741521465749826061515830447550861,
	        0.9258747122872904292046909607697858626672,
	        0.9214287029762026134209634491584644007645,
	        0.9170040432046712317435415947941667461407,
	        0.9126006304531540657099452867877830194818,
	        0.9082183626944031924279067014123113094560,
	        0.9038571383911010091985145255388756529519,
	        0.8995168564935076098442888811876009946339,
	        0.8951974164371194582318032579854959087286,
	        0.8908987181403393047402262055905414183192,
	        0.8866206620021572916876550405654798379036,
	        0.8823631488998431939863624175501337704454,
	        0.8781260801866497415560803096876886684788,
	        0.8739093576895269702812107160640808580937,
	        0.8697128837068475485533842136704059167642,
	        0.8655365610061430266950922187780245940470,
	        0.8613802928218509568132024098758678171240,
	    },
	    {
	        1.000000000000000000000000000000000000000,
	        0.8572439828530728308830350554160731167033,
	        0.7348672461377994256921043490917256989374,
	        0.6299605249474365823836053036391959460526,
	        0.5400298694461530849364654156443919196999,
	        0.4629373561436452146023454803849830673216,
	        0.3968502629920498686879264098181800898090,
	        0.3401975000435942410639200938313063115835,
	        0.2916322598940291452234231586652679613355,
	        0.2500000000000000000000000000000973522517,
	        0.2143109957132682077207587638541017338078,
	        0.1837168115344498564230260872730029657154,
	        0.1574901312368591455959013259098603145887,
	        0.1350074673615382712341163539111505530487,
	        0.1157343390359113036505863700962908348244,
	        0.09921256574801246717198160245458365671892,
	        0.08504937501089856026598002345785969688852,
	        0.07290806497350728630585578966634538139103,
	        0.06250000000000000000000000000004867612583,
	        0.05357774892831705193018969096354629710993,
	        0.04592920288361246410575652181826862667413,
	        0.03937253280921478639897533147748041066606,
	        0.03375186684038456780852908847780078154311,
	        0.02893358475897782591264659252408397570460,
	        0.02480314143700311679299540061365557274640,
	        0.02126234375272464006649500586447320397029,
	        0.01822701624337682157646394741659344311205,
	        0.01562500000000000000000000000001825354719,
	        0.01339443723207926298254742274089179019198,
	        0.01148230072090311602643913045457162797985,
	        0.009843133202303696599743832869373935671238,
	        0.008437966710096141952132272119453481206014,
	    },
	    {
	        1.000000000000000000000000000000000000000,
	        0.007233396189744456478161648131023810675775,
	        5.232202043780962102557587008169005410143E-5,
	        3.784659032745836912993682954976324658164E-7,
	        2.737593822694567686662466634421542264066E-9,
	        1.980210072614684707158711353745069372717E-11,
	        1.432364399414465384287735340977513952565E-13,
	        1.036085918905020069841154248521752033776E-15,
	        7.494419938055456100418425186702743722723E-18,
	        5.421010862427522170037264004417260251684E-20,
	        3.921231931684654880817938739668273317360E-22,
	        2.836382411375207747860568187463889509638E-24,
	        2.051667772709962123314993704273413823620E-26,
	        1.484052584974173558955043468582713624191E-28,
	        1.073474031353259824558654154333806911547E-30,
	        7.764862968180290824468612020607860317513E-33,
	        5.616633020792314645332222710264644852793E-35,
	        4.062733189179202535382045195211707654781E-37,
	        2.938735877055718769921841343128853888538E-39,
	        2.125704089576016965228859756656407540404E-41,
	        1.537605986206336992222535387300608525931E-43,
	        1.112211328195318530448364746285024038827E-45,
	        8.045065183558638234146057828832053516826E-48,
	        5.819314384499884015403474144560288801662E-50,
	        4.209340649576656799996170991423257963815E-52,
	        3.044782861598424467581974062513986546956E-54,
	        2.202412074968526631812431321732133496007E-56,
	        1.593091911132452277028880397827266782094E-58,
	        1.152346495989819456843455045622426762614E-60,
	        8.335378753358135655955994470664225877261E-63,
	        6.029309691461763611680553229574282672923E-65,
	        4.361238574900884540660050746922306538111E-67,
	    },
	};

	// Compute the actual Bernoulli parameter c = exp(-t/f):
	double c = 4611686018427387904.0; // This yields a fraction of 2^62, to keep only 62 bits of precision in this implementation

	for (int64_t i = 0, s = t; i < 3; i++, s >>= 5) {
		c *= exp[i][s & 31];
	}
	// Sample from Bernoulli_c
	return (uint32_t)((uint64_t)((r & 0x3FFFFFFFFFFFFFFFLL) - round_double(c)) >> 63);
}

static void sample_gauss_poly(int64_t *x, const unsigned char *seed, int nonce) { // Gaussian sampler
	static const int64_t cdt[14][3] = {
	    {0x0000020000000000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000030000000000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032000000000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032100000000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032102000000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032102010000LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0000000000000000LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0100000000000000LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0100020000000000LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0100020001000000LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0100020001000020LL, 0x0000000000000000LL},
	    {0x0000032102010020LL, 0x0100020001000020LL, 0x0001000000000000LL},
	    {0x0000032102010020LL, 0x0100020001000020LL, 0x0001000002000000LL},
	    {0x0000032102010020LL, 0x0100020001000020LL, 0x0001000002000001LL},
	};

	unsigned char seed_ex[PARAM_N * 8];
	int64_t i, j = 0, x_ind;
	int64_t *buf = (int64_t *) seed_ex;
	int64_t sign, k, /* (OQS note: unused) l, */ bitsremained, rbits, y, z;
	uint64_t r, s, t, c;
	int16_t dmsp = (int16_t)(nonce << 8);

	OQS_SHA3_cshake256_simple(seed_ex, PARAM_N * 8, dmsp++, seed, CRYPTO_RANDOMBYTES);

	for (x_ind = 0; x_ind < PARAM_N; x_ind++) {
		if ((j + 46) > (PARAM_N)) {
			OQS_SHA3_cshake256_simple((uint8_t *) buf, PARAM_N * 8, dmsp++, seed, CRYPTO_RANDOMBYTES);
			j = 0;
		}
		do {
			rbits = buf[j++];
			bitsremained = 64;
			do {
				// Sample x from D^+_{\sigma_2} and y from U({0, ..., k-1}):
				do {
					r = buf[j++];
					s = buf[j++];
					t = buf[j++];
					if (bitsremained <= 64 - 6) {
						rbits = (rbits << 6) ^ ((r >> 58) & 63);
						bitsremained += 6;
					}
					r &= 0x000003FFFFFFFFFFLL;
				} while (r > 0x0000032102010020LL); // Checking if r exceeds a maximum value. Variation is random and does not depend on private data
				y = 0;
				for (i = 0; i < 14; i++) {
					c = t - cdt[i][2];
					uint64_t b = (((c & cdt[i][2]) & 1) + (cdt[i][2] >> 1) + (c >> 1)) >> 63;
					// Least significant bits of all cdt[i][1] are zero: overflow cannot occur at this point
					c = s - (cdt[i][1] + b);
					b = (((c & b) & 1) + ((cdt[i][1]) >> 1) + (c >> 1)) >> 63;
					// Least significant bits of all cdt[i][0] are zero: overflow cannot occur at this point
					c = r - (cdt[i][0] + b);
					y += ~(c >> (63)) & 1LL;
				}
				// The next sampler works exclusively for PARAM_Xi <= 28
				do {
					do {
						if (bitsremained < 6) {
							rbits = buf[j++];
							bitsremained = 64;
						}
						z = rbits & 63;
						rbits >>= 6;
						bitsremained -= 6;
					} while (z == 63);
					if (bitsremained < 2) {
						rbits = buf[j++];
						bitsremained = 64;
					}
					z = (mod7(z) << 2) + (rbits & 3);
					rbits >>= 2;
					bitsremained -= 2;
				} while (z >= PARAM_Xi); // Making sure random z does not exceed a certain limit. No private data leaked, it varies uniformly
				k = PARAM_Xi * y + z;
				// Sample a bit from Bernoulli_{exp(-y*(y + 2*k*x)/(2*k^2*sigma_2^2))}
			} while (Bernoulli(buf[j++], z * ((k << 1) - z)) == 0);
			// Put last randombits into sign bit
			rbits <<= (64 - bitsremained);
			if (bitsremained == 0LL) {
				rbits = buf[j++];
				bitsremained = 64;
			}
			sign = rbits >> 63;
			rbits <<= 1;
			bitsremained--;
		} while ((k | (sign & 1)) == 0);
		if (bitsremained == 0LL) {
			rbits = buf[j++];
			bitsremained = 64;
		}
		sign = rbits >> 63;
		rbits <<= 1;
		bitsremained--;
		k = ((k << 1) & sign) - k;
		x[x_ind] = (k << 48) >> 48;
	}
}

static void encode_c(uint32_t *pos_list, int16_t *sign_list, unsigned char *c_bin) { // Encoding of c' by mapping the output of the hash function H to an N-element vector with entries {-1,0,1}
	int i, pos, cnt = 0;
	int16_t c[PARAM_N];
	const int RLENGTH = OQS_SHA3_SHAKE128_RATE;
	unsigned char r[OQS_SHA3_SHAKE128_RATE]; /* OQS note: was RLENGTH but it was failing on macOS */
	uint16_t dmsp = 0;

	// Use the hash value as key to generate some randomness
	OQS_SHA3_cshake128_simple(r, RLENGTH, dmsp++, c_bin, CRYPTO_RANDOMBYTES);

	// Use rejection sampling to determine positions to be set in the new vector
	for (i = 0; i < PARAM_N; i++)
		c[i] = 0;

	for (i = 0; i < PARAM_W;) { // Sample a unique position k times. Use two bytes
		if (cnt > (RLENGTH - 3)) {
			OQS_SHA3_cshake128_simple(r, RLENGTH, dmsp++, c_bin, CRYPTO_RANDOMBYTES);
			cnt = 0;
		}
		pos = (r[cnt] << 8) | (r[cnt + 1]);
		pos = pos & (PARAM_N - 1); // Position is in the range [0,N-1]

		if (c[pos] == 0) { // Position has not been set yet. Determine sign
			if ((r[cnt + 2] & 1) == 1)
				c[pos] = -1;
			else
				c[pos] = 1;
			pos_list[i] = pos;
			sign_list[i] = c[pos];
			i++;
		}
		cnt += 3;
	}
}

/* sign.c */

#ifdef DEBUG
unsigned long long rejwctr;
unsigned long long rejyzctr;
unsigned long long ctr_keygen;
unsigned long long ctr_sign;
#endif

static void pack_sk(unsigned char *sk, poly s, poly e, unsigned char *seeds) { // Pack secret key sk
	int i;
	int16_t *isk = (int16_t *) sk;

	for (i = 0; i < PARAM_N; i++)
		isk[i] = s[i];

	isk += PARAM_N;
	for (i = 0; i < (PARAM_N); i++)
		isk[i] = e[i];

	memcpy(&isk[PARAM_N], seeds, 2 * CRYPTO_SEEDBYTES);
}

static void encode_pk(unsigned char *pk, const poly t, const unsigned char *seedA) { // Encode public key pk
	unsigned int i, j = 0;
	uint32_t *pt = (uint32_t *) pk;

	for (i = 0; i < (PARAM_N * PARAM_Q_LOG / 32); i += (PARAM_Q_LOG / 8)) {
		pt[i] = t[j] | (t[j + 1] << 24);
		pt[i + 1] = (t[j + 1] >> 8) | (t[j + 2] << 16);
		pt[i + 2] = (t[j + 2] >> 16) | (t[j + 3] << 8);
		j += 4;
	}
	memcpy(&pk[PARAM_N * PARAM_Q_LOG / 8], seedA, CRYPTO_SEEDBYTES);
}

static void decode_pk(int32_t *pk, unsigned char *seedA, const unsigned char *pk_in) { // Decode public key pk
	unsigned int i, j = 0;
	uint32_t *pt = (uint32_t *) pk_in, *pp = (uint32_t *) pk, mask24 = (1 << PARAM_Q_LOG) - 1;

	for (i = 0; i < PARAM_N; i += 4) {
		pp[i] = pt[j] & mask24;
		pp[i + 1] = ((pt[j] >> 24) | (pt[j + 1] << 8)) & mask24;
		pp[i + 2] = ((pt[j + 1] >> 16) | (pt[j + 2] << 16)) & mask24;
		pp[i + 3] = pt[j + 2] >> 8;
		j += 3;
	}
	memcpy(seedA, &pk_in[PARAM_N * PARAM_Q_LOG / 8], CRYPTO_SEEDBYTES);
}

static void encode_sig(unsigned char *sm, unsigned char *c, poly z) { // Encode signature sm
	unsigned int i, j = 0;
	uint64_t *t = (uint64_t *) z;
	uint32_t *pt = (uint32_t *) sm;

	for (i = 0; i < (PARAM_N * PARAM_D / 32); i += (PARAM_D / 2)) {
		pt[i] = (t[j] & ((1 << 22) - 1)) | (t[j + 1] << 22);
		pt[i + 1] = ((t[j + 1] >> 10) & ((1 << 12) - 1)) | (t[j + 2] << 12);
		pt[i + 2] = ((t[j + 2] >> 20) & ((1 << 2) - 1)) | ((t[j + 3] & ((1 << 22) - 1)) << 2) | (t[j + 4] << 24);
		pt[i + 3] = ((t[j + 4] >> 8) & ((1 << 14) - 1)) | (t[j + 5] << 14);
		pt[i + 4] = ((t[j + 5] >> 18) & ((1 << 4) - 1)) | ((t[j + 6] & ((1 << 22) - 1)) << 4) | (t[j + 7] << 26);
		pt[i + 5] = ((t[j + 7] >> 6) & ((1 << 16) - 1)) | (t[j + 8] << 16);
		pt[i + 6] = ((t[j + 8] >> 16) & ((1 << 6) - 1)) | ((t[j + 9] & ((1 << 22) - 1)) << 6) | (t[j + 10] << 28);
		pt[i + 7] = ((t[j + 10] >> 4) & ((1 << 18) - 1)) | (t[j + 11] << 18);
		pt[i + 8] = ((t[j + 11] >> 14) & ((1 << 8) - 1)) | ((t[j + 12] & ((1 << 22) - 1)) << 8) | (t[j + 13] << 30);
		pt[i + 9] = ((t[j + 13] >> 2) & ((1 << 20) - 1)) | (t[j + 14] << 20);
		pt[i + 10] = ((t[j + 14] >> 12) & ((1 << 10) - 1)) | (t[j + 15] << 10);
		j += 16;
	}
	memcpy(&sm[PARAM_N * PARAM_D / 8], c, CRYPTO_C_BYTES);
}

static void decode_sig(unsigned char *c, poly z, const unsigned char *sm) { // Decode signature sm
	unsigned int i, j = 0;
	uint32_t *pt = (uint32_t *) sm;

	for (i = 0; i < PARAM_N; i += 16) {
		z[i] = ((int32_t) pt[j + 0] << 10) >> 10;
		z[i + 1] = (int32_t)(pt[j + 0] >> 22) | ((int32_t)(pt[j + 1] << 20) >> 10);
		z[i + 2] = (int32_t)(pt[j + 1] >> 12) | ((int32_t)(pt[j + 2] << 30) >> 10);
		z[i + 3] = (int32_t)(pt[j + 2] << 8) >> 10;
		z[i + 4] = (int32_t)(pt[j + 2] >> 24) | ((int32_t)(pt[j + 3] << 18) >> 10);
		z[i + 5] = (int32_t)(pt[j + 3] >> 14) | ((int32_t)(pt[j + 4] << 28) >> 10);
		z[i + 6] = (int32_t)(pt[j + 4] << 6) >> 10;
		z[i + 7] = (int32_t)(pt[j + 4] >> 26) | ((int32_t)(pt[j + 5] << 16) >> 10);
		z[i + 8] = (int32_t)(pt[j + 5] >> 16) | ((int32_t)(pt[j + 6] << 26) >> 10);
		z[i + 9] = (int32_t)(pt[j + 6] << 4) >> 10;
		z[i + 10] = (int32_t)(pt[j + 6] >> 28) | ((int32_t)(pt[j + 7] << 14) >> 10);
		z[i + 11] = (int32_t)(pt[j + 7] >> 18) | ((int32_t)(pt[j + 8] << 24) >> 10);
		z[i + 12] = (int32_t)(pt[j + 8] << 2) >> 10;
		z[i + 13] = (int32_t)(pt[j + 8] >> 30) | ((int32_t)(pt[j + 9] << 12) >> 10);
		z[i + 14] = (int32_t)(pt[j + 9] >> 20) | ((int32_t)(pt[j + 10] << 22) >> 10);
		z[i + 15] = (int32_t) pt[j + 10] >> 10;
		j += 11;
	}
	memcpy(c, &sm[PARAM_N * PARAM_D / 8], CRYPTO_C_BYTES);
}

static void hash_vm(unsigned char *c_bin, poly v, const unsigned char *m, unsigned long long mlen) { // Hash to generate c'
	unsigned char t[PARAM_N + mlen];
	int64_t mask, cL;
	unsigned int i;

	for (i = 0; i < PARAM_N; i++) {
		// If v[i] > PARAM_Q/2 then v[i] -= PARAM_Q
		mask = (int64_t)(PARAM_Q / 2 - v[i]) >> 63;
		v[i] = ((v[i] - PARAM_Q) & mask) | (v[i] & ~mask);

		cL = v[i] & ((1 << PARAM_D) - 1);
		// If cL > 2^(d-1) then cL -= 2^d
		mask = (int64_t)((1 << (PARAM_D - 1)) - cL) >> 63;
		cL = ((cL - (1 << PARAM_D)) & mask) | (cL & ~mask);
		t[i] = (unsigned char) ((v[i] - cL) >> PARAM_D);
	}
	memcpy(&t[PARAM_N], m, mlen);
	OQS_SHA3_shake256(c_bin, CRYPTO_C_BYTES, t, mlen + PARAM_N);
}

static __inline uint64_t Abs(int64_t value) { // Compute absolute value

	uint64_t mask = (uint64_t)(value >> 63);
	return ((mask ^ value) - mask);
}

static int test_rejection(poly z) { // Check bounds for signature vector z during signing. Returns 0 if valid, otherwise outputs 1 if invalid (rejected).
	// This function leaks the position of the coefficient that fails the test (but this is independent of the secret data).
	// It does not leak the sign of the coefficients.
	unsigned int i;

	for (i = 0; i < PARAM_N; i++) {
		if (Abs(z[i]) > (PARAM_B - PARAM_U))
			return 1;
	}
	return 0;
}

static int test_v(poly v) { // Check bounds for w = v - ec during signature verification. Returns 0 if valid, otherwise outputs 1 if invalid (rejected).
	// This function leaks the position of the coefficient that fails the test (but this is independent of the secret data).
	// It does not leak the sign of the coefficients.
	unsigned int i;
	int64_t mask, left, val;
	uint64_t t0, t1;

	for (i = 0; i < PARAM_N; i++) {
		// If v[i] > PARAM_Q/2 then v[i] -= PARAM_Q
		mask = (int64_t)(PARAM_Q / 2 - v[i]) >> 63;
		val = ((v[i] - PARAM_Q) & mask) | (v[i] & ~mask);
		// If (Abs(val) < PARAM_Q/2 - PARAM_REJECTION) then t0 = 0, else t0 = 1
		t0 = (uint64_t)(~((int64_t) Abs(val) - (int64_t)(PARAM_Q / 2 - PARAM_REJECTION))) >> 63;

		left = val;
		val = (int32_t)((val + (1 << (PARAM_D - 1)) - 1) >> PARAM_D);
		val = left - (val << PARAM_D);
		// If (Abs(val) < (1<<(PARAM_D-1))-PARAM_REJECTION) then t1 = 0, else t1 = 1
		t1 = (uint64_t)(~((int64_t) Abs(val) - (int64_t)((1 << (PARAM_D - 1)) - PARAM_REJECTION))) >> 63;

		if ((t0 | t1) == 1) // Returns 1 if any of the two tests failed
			return 1;
	}
	return 0;
}

static int test_z(poly z) { // Check bounds for signature vector z during signature verification
	// Returns 0 if valid, otherwise outputs 1 if invalid (rejected)
	unsigned int i;

	for (i = 0; i < PARAM_N; i++) {
		if (z[i] < -(PARAM_B - PARAM_U) || z[i] > (PARAM_B - PARAM_U))
			return 1;
	}
	return 0;
}

static int check_ES(poly p, int bound) { // Checks the generated polynomial e or s
	// Returns 0 if ok, otherwise returns 1
	unsigned int i, j, sum = 0, limit = PARAM_N;
	int16_t temp, mask, list[PARAM_N];

	for (j = 0; j < PARAM_N; j++)
		list[j] = (int16_t)(Abs(p[j]));

	for (j = 0; j < PARAM_W; j++) {
		for (i = 0; i < limit - 1; i++) {
			// If list[i+1] > list[i] then exchange contents
			mask = (list[i + 1] - list[i]) >> 15;
			temp = (list[i + 1] & mask) | (list[i] & ~mask);
			list[i + 1] = (list[i] & mask) | (list[i + 1] & ~mask);
			list[i] = temp;
		}
		sum += list[limit - 1];
		limit -= 1;
	}

	if ((int) sum > bound)
		return 1;
	return 0;
}

/********************************************************************************************
* Name:        sparse_mul16
* Description: performs sparse polynomial multiplication
* Parameters:  inputs:
*              - const unsigned char* sk: part of the secret key
*              - const uint32_t pos_list[PARAM_W]: list of indices of nonzero elements in c
*              - const int16_t sign_list[PARAM_W]: list of signs of nonzero elements in c
*              outputs:
*              - poly prod: product of 2 polynomials
*
* Note: pos_list[] and sign_list[] contain public information since c is public
*********************************************************************************************/
static void sparse_mul16(poly prod, const unsigned char *sk, const uint32_t pos_list[PARAM_W], const int16_t sign_list[PARAM_W]) {
	int i, j, pos;
	int16_t *t = (int16_t *) sk;

	for (i = 0; i < PARAM_N; i++)
		prod[i] = 0;

	for (i = 0; i < PARAM_W; i++) {
		pos = pos_list[i];
		for (j = 0; j < pos; j++) {
			prod[j] = prod[j] - sign_list[i] * t[j + PARAM_N - pos];
		}
		for (j = pos; j < PARAM_N; j++) {
			prod[j] = prod[j] + sign_list[i] * t[j - pos];
		}
	}
}

/********************************************************************************************
* Name:        sparse_mul32
* Description: performs sparse polynomial multiplication 
* Parameters:  inputs:
*              - const int32_t* pk: part of the public key
*              - const uint32_t pos_list[PARAM_W]: list of indices of nonzero elements in c
*              - const int16_t sign_list[PARAM_W]: list of signs of nonzero elements in c
*              outputs:
*              - poly prod: product of 2 polynomials
*********************************************************************************************/
static void sparse_mul32(poly prod, const int32_t *pk, const uint32_t pos_list[PARAM_W], const int16_t sign_list[PARAM_W]) {
	int i, j, pos;

	for (i = 0; i < PARAM_N; i++)
		prod[i] = 0;

	for (i = 0; i < PARAM_W; i++) {
		pos = pos_list[i];
		for (j = 0; j < pos; j++) {
			prod[j] = prod[j] - sign_list[i] * pk[j + PARAM_N - pos];
		}
		for (j = pos; j < PARAM_N; j++) {
			prod[j] = prod[j] + sign_list[i] * pk[j - pos];
		}
	}
	for (i = 0; i < PARAM_N; i++)
		prod[i] = barr_reduce(prod[i]);
}

#include "qTESLA_api.c"

int oqs_qTESLA_III_speed_crypto_sign_keypair(OQS_RAND *rand, unsigned char *pk, unsigned char *sk) {
	return crypto_sign_keypair(rand, pk, sk);
}

int oqs_qTESLA_III_speed_crypto_sign(OQS_RAND *rand, unsigned char *sm, unsigned long long *smlen, const unsigned char *m, unsigned long long mlen, const unsigned char *sk) {
	return crypto_sign(rand, sm, smlen, m, mlen, sk);
}

int oqs_qTESLA_III_speed_crypto_verify(unsigned char *m, unsigned long long mlen, const unsigned char *sm, unsigned long long smlen, const unsigned char *pk) {
	return crypto_verify(m, mlen, sm, smlen, pk);
}
